home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqbuild / region.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  11.1 KB  |  505 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. /*
  5.  * 
  6.  * input
  7.  * -----
  8.  * vertexes
  9.  * edges
  10.  * faces
  11.  * 
  12.  * output
  13.  * ------
  14.  * smaller set of vertexes
  15.  * smaller set of edges
  16.  * regions
  17.  * ? triangulated regions
  18.  * face to region mapping numbers
  19.  * 
  20.  */
  21.  
  22. typedef struct {
  23.   int numedges;
  24.   int edges[2];
  25. } __packed checkpoint_t;                // 12
  26.  
  27. int firstedge;                        // 4
  28.  
  29. vec3_t region_mins, region_maxs;            // 24
  30.  
  31. /* changed by niels */
  32. #ifdef EDGEMAPPING
  33. int edgemapping[MAX_MAP_EDGES];                // 172032
  34. #endif
  35.  
  36. checkpoint_t *checkpoints;
  37.  
  38. void AddPointToRegion(register vec3_t p)
  39. {
  40.   short int i;
  41.  
  42.   for (i = 0; i < 3; i++) {
  43.     if (p[i] < region_mins[i])
  44.       region_mins[i] = p[i];
  45.     if (p[i] > region_maxs[i])
  46.       region_maxs[i] = p[i];
  47.   }
  48. }
  49.  
  50. void ClearRegionSize(void)
  51. {
  52.   region_mins[0] = region_mins[1] = region_mins[2] = 9999;
  53.   region_maxs[0] = region_maxs[1] = region_maxs[2] = -9999;
  54. }
  55.  
  56. void AddFaceToRegionSize(register struct visfacet * f)
  57. {
  58.   int i;
  59.  
  60.   for (i = 0; i < f->numpoints; i++)
  61.     AddPointToRegion(f->pts[i]);
  62. }
  63.  
  64. /*
  65.  * ==============
  66.  * CanJoinFaces
  67.  * ==============
  68.  */
  69. bool CanJoinFaces(__memBase, register struct visfacet * f, register struct visfacet * f2)
  70. {
  71.   vec3_t oldmins, oldmaxs;
  72.   short int i;
  73.  
  74.   if (f2->planenum != f->planenum
  75.       || f2->planeside != f->planeside
  76.       || f2->texturenum != f->texturenum)
  77.     return FALSE;
  78.   if (f2->outputnumber != -1)
  79.     return FALSE;
  80.   if (f2->contents[0] != f->contents[0]) {                       // does this ever happen? theyy shouldn't share.
  81.  
  82.     eprintf("CanJoinFaces: edge with different contents");
  83.     return FALSE;
  84.   }
  85.  
  86. // check size constraints
  87.   if (!(bspMem->texinfo[f->texturenum].flags & TEX_SPECIAL)) {
  88.     VectorCopy(region_mins, oldmins);
  89.     VectorCopy(region_maxs, oldmaxs);
  90.     AddFaceToRegionSize(f2);
  91.     for (i = 0; i < 3; i++) {
  92.       if (region_maxs[i] - region_mins[i] > 240) {
  93.     VectorCopy(oldmins, region_mins);
  94.     VectorCopy(oldmaxs, region_maxs);
  95.     return FALSE;
  96.       }
  97.     }
  98.   }
  99.   else {
  100.     if (bspMem->numsurfedges - firstedge + f2->numpoints > MAX_EDGES_IN_REGION)
  101.       return FALSE;                                   // a huge water or sky polygon
  102.  
  103.   }
  104.  
  105. // check edge count constraints
  106.   return TRUE;
  107. }
  108.  
  109. /*
  110.  * ==============
  111.  * RecursiveGrowRegion
  112.  * ==============
  113.  */
  114. void RecursiveGrowRegion(__memBase, register struct dface_t * r, register struct visfacet * f)
  115. {
  116.   int e;
  117.   struct visfacet *f2;
  118.   int i;
  119.  
  120.   if (f->outputnumber == bspMem->numfaces)
  121.     return;
  122.  
  123.   if (f->outputnumber != -1)
  124.     Error("RecursiveGrowRegion: region collision");
  125.   f->outputnumber = bspMem->numfaces;
  126.  
  127. // add edges    
  128.   for (i = 0; i < f->numpoints; i++) {
  129.     e = f->edges[i];
  130. /*  if (!edgefaces[abs(e)][0]) */
  131.     if (!bspMem->edgefaces[0][abs(e)])
  132.       continue;                                       // edge has allready been removed
  133.  
  134.     if (e > 0)
  135. /*    f2 = edgefaces[e][1]; */
  136.       f2 = bspMem->edgefaces[1][e];
  137.     else
  138. /*    f2 = edgefaces[-e][0]; */
  139.       f2 = bspMem->edgefaces[0][-e];
  140.     if (f2 && f2->outputnumber == bspMem->numfaces) {
  141. /*    edgefaces[abs(e)][0] = NULL; */
  142.       bspMem->edgefaces[0][abs(e)] = NULL;
  143. /*    edgefaces[abs(e)][1] = NULL; */
  144.       bspMem->edgefaces[1][abs(e)] = NULL;
  145.       continue;                                       // allready merged
  146.  
  147.     }
  148.     if (f2 && CanJoinFaces(bspMem, f, f2)) {                           // remove the edge and merge the faces
  149.  
  150. /*    edgefaces[abs(e)][0] = NULL; */
  151.       bspMem->edgefaces[0][abs(e)] = NULL;
  152. /*    edgefaces[abs(e)][1] = NULL; */
  153.       bspMem->edgefaces[1][abs(e)] = NULL;
  154.       RecursiveGrowRegion(bspMem, r, f2);
  155.     }
  156.     else {
  157.       // emit a surfedge
  158.       if (bspMem->numsurfedges == bspMem->max_numsurfedges)
  159.         ExpandClusters(bspMem, LUMP_SURFEDGES);
  160.       bspMem->dsurfedges[bspMem->numsurfedges] = e;
  161.       bspMem->numsurfedges++;
  162.     }
  163.   }
  164.  
  165. }
  166.  
  167. #ifdef DEBUG
  168. void PrintDface(register int f)
  169. {                                           // for debugging
  170.  
  171.   struct dface_t *df;
  172.   struct dedge_t *e;
  173.   int i, n;
  174.  
  175.   df = &bspMem->dfaces[f];
  176.   for (i = 0; i < df->numedges; i++) {
  177.     n = bspMem->dsurfedges[df->firstedge + i];
  178.     e = &bspMem->dedges[abs(n)];
  179.     if (n < 0)
  180.       mprintf("%5i  =  %5i : %5i\n", n, e->v[1], e->v[0]);
  181.     else
  182.       mprintf("%5i  =  %5i : %5i\n", n, e->v[0], e->v[1]);
  183.   }
  184. }
  185.  
  186. void FindVertexUse(register int v)
  187. {                                           // for debugging
  188.  
  189.   int i, j, n;
  190.   struct dface_t *df;
  191.   struct dedge_t *e;
  192.  
  193.   for (i = firstmodelface; i < bspMem->numfaces; i++) {
  194.     df = &bspMem->dfaces[i];
  195.     for (j = 0; j < df->numedges; j++) {
  196.       n = bspMem->dsurfedges[df->firstedge + j];
  197.       e = &bspMem->dedges[abs(n)];
  198.       if (e->v[0] == v || e->v[1] == v) {
  199.     mprintf("on face %i\n", i);
  200.     break;
  201.       }
  202.     }
  203.   }
  204. }
  205.  
  206. void FindEdgeUse(register int v)
  207. {                                           // for debugging
  208.  
  209.   int i, j, n;
  210.   struct dface_t *df;
  211.  
  212.   for (i = firstmodelface; i < bspMem->numfaces; i++) {
  213.     df = &bspMem->dfaces[i];
  214.     for (j = 0; j < df->numedges; j++) {
  215.       n = bspMem->dsurfedges[df->firstedge + j];
  216.       if (n == v || -n == v) {
  217.     mprintf("on face %i\n", i);
  218.     break;
  219.       }
  220.     }
  221.   }
  222. }
  223. #endif
  224.  
  225. /*
  226.  * ================
  227.  * HealEdges
  228.  * 
  229.  * Extends e1 so that it goes all the way to e2, and removes all references
  230.  * to e2
  231.  * ================
  232.  */
  233. void HealEdges(register int e1, int register e2)
  234. {
  235.   int i, j, n, saved;
  236.   struct dface_t *df;
  237.   struct dedge_t *ed, *ed2;
  238.   vec3_t v1, v2;
  239.   struct dface_t *found[2];
  240.   int foundj[2];
  241.  
  242.   /*
  243.    * FIX!!! why this? niels
  244.    */
  245. /* changed by niels */
  246. #ifdef EDGEMAPPING
  247.   e1 = edgemapping[e1];
  248.   e2 = edgemapping[e2];
  249.  
  250. // extend e1 to e2
  251.   ed = &bspMem->dedges[e1];
  252.   ed2 = &bspMem->dedges[e2];
  253.   VectorSubtract(bspMem->dvertexes[ed->v[1]].point, bspMem->dvertexes[ed->v[0]].point, v1);
  254.   VectorNormalize(v1);
  255.  
  256.   if (ed->v[0] == ed2->v[0])
  257.     ed->v[0] = ed2->v[1];
  258.   else if (ed->v[0] == ed2->v[1])
  259.     ed->v[0] = ed2->v[0];
  260.   else if (ed->v[1] == ed2->v[0])
  261.     ed->v[1] = ed2->v[1];
  262.   else if (ed->v[1] == ed2->v[1])
  263.     ed->v[1] = ed2->v[0];
  264.   else
  265.     Error("HealEdges: edges don't meet");
  266.  
  267.   VectorSubtract(bspMem->dvertexes[ed->v[1]].point, bspMem->dvertexes[ed->v[0]].point, v2);
  268.   VectorNormalize(v2);
  269.  
  270.   if (!VectorCompare(v1, v2))
  271.     Error("HealEdges: edges not colinear");
  272.  
  273.   edgemapping[e2] = e1;
  274.   saved = 0;
  275.  
  276. // remove all uses of e2
  277.   for (i = firstmodelface; i < bspMem->numfaces; i++) {
  278.     df = &bspMem->dfaces[i];
  279.     for (j = 0; j < df->numedges; j++) {
  280.       n = bspMem->dsurfedges[df->firstedge + j];
  281.       if (n == e2 || n == -e2) {
  282.     found[saved] = df;
  283.     foundj[saved] = j;
  284.     saved++;
  285.     break;
  286.       }
  287.     }
  288.   }
  289.  
  290.   if (saved != 2)
  291.     eprintf("didn't find both faces for a saved edge\n");
  292.   else {
  293.     for (i = 0; i < 2; i++) {                               // remove this edge
  294.  
  295.       df = found[i];
  296.       j = foundj[i];
  297.       for (j++; j < df->numedges; j++)
  298.     bspMem->dsurfedges[df->firstedge + j - 1] =
  299.       bspMem->dsurfedges[df->firstedge + j];
  300.       bspMem->dsurfedges[df->firstedge + j - 1] = 0;
  301.       df->numedges--;
  302.     }
  303.  
  304. /*  edgefaces[e2][0] = edgefaces[e2][1] = NULL; */
  305.     bspMem->edgefaces[0][e2] = bspMem->edgefaces[1][e2] = NULL;
  306.   }
  307. #else
  308.   return;
  309. #endif
  310. }
  311.  
  312. /*
  313.  * ==============
  314.  * RemoveColinearEdges
  315.  * ==============
  316.  */
  317. void RemoveColinearEdges(__memBase)
  318. {
  319.   int i, v;
  320.   short int j;
  321.   int c0, c1, c2, c3;
  322.   checkpoint_t *cp;
  323.  
  324. /* changed by niels */
  325. #ifdef EDGEMAPPING
  326. // no edges remapped yet
  327.   for (i = 0; i < bspMem->numedges; i++)
  328.     edgemapping[i] = i;
  329. #endif
  330.  
  331. // find vertexes that only have two edges
  332.   /* added by niels */
  333.   if(!(checkpoints = (checkpoint_t *)tmalloc(sizeof(checkpoint_t) * bspMem->numvertexes)))
  334.     Error("RemoveColinearEdges: failed to allocate checkpoints!\n");
  335.  
  336.   for (i = firstmodeledge; i < bspMem->numedges; i++) {
  337. /*  if (!edgefaces[i][0]) */
  338.     if (!bspMem->edgefaces[0][i])
  339.       continue;                                       // removed
  340.  
  341.     for (j = 0; j < 2; j++) {
  342.       v = bspMem->dedges[i].v[j];
  343.       cp = &checkpoints[v];
  344.       if (cp->numedges < 2)
  345.     cp->edges[cp->numedges] = i;
  346.       cp->numedges++;
  347.     }
  348.   }
  349.  
  350. // if a vertex only has two edges and they are colinear, it can be removed
  351.   c0 = c1 = c2 = c3 = 0;
  352.  
  353.   for (i = 0; i < bspMem->numvertexes; i++) {
  354.     cp = &checkpoints[i];
  355.     switch (cp->numedges) {
  356.       case 0:
  357.     c0++;
  358.     break;
  359.       case 1:
  360.     c1++;
  361.     break;
  362.       case 2:
  363.     c2++;
  364.     HealEdges(cp->edges[0], cp->edges[1]);
  365.     break;
  366.       default:
  367.     c3++;
  368.     break;
  369.     }
  370.   }
  371.  
  372.   //      mprintf ("%5i c0\n", c0);
  373.   //      mprintf ("%5i c1\n", c1);
  374.   //      mprintf ("%5i c2\n", c2);
  375.   //      mprintf ("%5i c3+\n", c3);
  376.   mprintf("%5i edges removed by tjunction healing\n", c2);
  377.   /* added by niels */
  378.   tfree(checkpoints);
  379. }
  380.  
  381. /*
  382.  * ==============
  383.  * CountRealNumbers
  384.  * ==============
  385.  */
  386. void CountRealNumbers(__memBase)
  387. {
  388.   int i;
  389.   int c;
  390.  
  391.   mprintf("%5i regions\n", bspMem->numfaces - firstmodelface);
  392.  
  393.   c = 0;
  394.   for (i = firstmodelface; i < bspMem->numfaces; i++)
  395.     c += bspMem->dfaces[i].numedges;
  396.   mprintf("%5i real marksurfaces\n", c);
  397.  
  398.   c = 0;
  399.   for (i = firstmodeledge; i < bspMem->numedges; i++)
  400. /*  if (edgefaces[i][0]) */
  401.     if (bspMem->edgefaces[0][i])
  402.       c++;                                       // not removed
  403.  
  404.   mprintf("%5i real edges\n", c);
  405. }
  406.  
  407. //=============================================================================
  408.  
  409. /*
  410.  * ==============
  411.  * GrowNodeRegion_r
  412.  * ==============
  413.  */
  414. void GrowNodeRegion_r(__memBase, register struct node * node)
  415. {
  416.   struct dface_t *r;
  417.   struct visfacet *f;
  418.   int i;
  419.  
  420.   if (node->planenum == PLANENUM_LEAF)
  421.     return;
  422.  
  423.   node->firstface = bspMem->numfaces;
  424.  
  425.   for (f = node->faces; f; f = f->next) {
  426. //              if (f->outputnumber != -1)
  427.     //                      continue;       // allready grown into an earlier region
  428.  
  429.     // emit a region
  430.  
  431.     if (bspMem->numfaces == bspMem->max_numfaces)
  432.       ExpandClusters(bspMem, LUMP_FACES);
  433.     f->outputnumber = bspMem->numfaces;
  434.     r = &bspMem->dfaces[bspMem->numfaces];
  435.  
  436.     r->planenum = node->outputplanenum;
  437.     r->side = f->planeside;
  438.     r->texinfo = f->texturenum;
  439.     for (i = 0; i < MAXLIGHTMAPS; i++)
  440.       r->styles[i] = 255;
  441.     r->lightofs = -1;
  442.  
  443.     // add the face and mergable neighbors to it
  444.  
  445. #if 0
  446.     ClearRegionSize();
  447.     AddFaceToRegionSize(f);
  448.     RecursiveGrowRegion(r, f);
  449. #endif
  450.     r->firstedge = firstedge = bspMem->numsurfedges;
  451.     for (i = 0; i < f->numpoints; i++) {
  452.       if (bspMem->numsurfedges == bspMem->max_numsurfedges)
  453.     ExpandClusters(bspMem, LUMP_SURFEDGES);
  454.       bspMem->dsurfedges[bspMem->numsurfedges] = f->edges[i];
  455.       bspMem->numsurfedges++;
  456.     }
  457.  
  458.     r->numedges = bspMem->numsurfedges - r->firstedge;
  459.  
  460.     bspMem->numfaces++;
  461.   }
  462.  
  463.   node->numfaces = bspMem->numfaces - node->firstface;
  464.  
  465.   GrowNodeRegion_r(bspMem, node->children[0]);
  466.   GrowNodeRegion_r(bspMem, node->children[1]);
  467. }
  468.  
  469. /*
  470.  * ==============
  471.  * GrowNodeRegions
  472.  * ==============
  473.  */
  474. void GrowNodeRegions(__memBase, struct node * headnode)
  475. {
  476.   mprintf("----- GrowRegions -------\n");
  477.  
  478.   GrowNodeRegion_r(bspMem, headnode);
  479.  
  480. //RemoveColinearEdges ();
  481.   CountRealNumbers(bspMem);
  482. }
  483.  
  484. /*
  485.  * ===============================================================================
  486.  * 
  487.  * Turn the faces on a plane into optimal non-convex regions
  488.  * The edges may still be split later as a result of tjunctions
  489.  * 
  490.  * typedef struct
  491.  * {
  492.  * vec3_t       dir;
  493.  * vec3_t       origin;
  494.  * vec3_t       p[2];
  495.  * } 
  496.  * for all faces
  497.  * for all edges
  498.  * for all edges so far
  499.  * if overlap
  500.  * split
  501.  * 
  502.  * 
  503.  * ===============================================================================
  504.  */
  505.